package b4.view.component.town
{
	import as3isolib.geom.Pt;
	
	import b4.config.LayerConfig;
	import b4.config.LayerItemConfig;

	public class PathFinding
	{
		//路点寻路算法 (A*算法） 
		/**
		 * 内部计算时与map对应 即每个格子对应一个(1,1)坐标  
		 * 与外部数据比较时注意先 标准化数据
		 * 返回时存储的也是标准化数据
		 */ 
		public static function findPathByAstar(layer:LayerConfig, startPos:Pt, destPos:Pt):Array
		{
			var startSTD:Pt = posToSTD(startPos);
			var destSTD:Pt = posToSTD(destPos);
			if (!checkAvaible(layer, destSTD)) return null;
			//开启列表   （之后应使用最大优先队列 提高速度 这里暂时使用数组）
			var openList:Array = new Array();
			//关闭列表 （使用hash）
			var closeListMap:Object = new Object();

			var estimateCost:int = estimate( startSTD, destSTD);
			var startNode:PathNode = new PathNode( startSTD, 0, estimateCost, 0 + estimateCost, null);
			var find:Boolean = false;
			openList.push(startNode);
			//当开启列表内还有节点
			var count:int = 0;
			while (openList.length > 0)
			{

				//step 1:寻找F值最小的节点
				var tempNodeIndex:int = 0;
				var finalCost:int = (openList[tempNodeIndex] as PathNode).finalCost;
				//\*\遍历数组 代价太高 可以改进
				for (var i:int =1; i<openList.length; i++)
				{

					if ((openList[i] as PathNode).finalCost < finalCost )
					{
						tempNodeIndex = i;
						finalCost = (openList[tempNodeIndex] as PathNode).finalCost;
					}
				}
				//获取节点   放入关闭列表  同时从开启列表中删除
				startNode = openList[tempNodeIndex] as PathNode;
				closeListMap[startNode.point.x + "_" + startNode.point.y] = 2;
				openList.splice(tempNodeIndex,1);
				//step 2:抵达目的地退出
				if (startNode.point.x == destSTD.x && startNode.point.y == destSTD.y )
				{
					find = true;
					break;
				}
				//step 3:根据该节点生成可能的新路径
				var direction:Object = direction(8);
				for (var key:String in direction)
				{
					//step 3.1:判断新的节点是否可用以及是否在关闭列表中
					var tmpSTD:Pt = new Pt(startNode.point.x + direction[key]['x'], startNode.point.y + direction[key]['y'], 0);
					if (!checkAvaible(layer, tmpSTD) || closeListMap[tmpSTD.x+"_"+tmpSTD.y] != null)
					{
						continue;
					}
					//step 3.2:计算当前历史节点的 F = G + H值
					var g:int = dist( startNode.point, tmpSTD);
					var h:int = estimate( tmpSTD, destSTD);
					var tempNode:PathNode = new PathNode(tmpSTD, g, h, g+h,startNode); 
					//step 3.3:判断新的节点是否在开启列表中 
					var exist:Boolean = false;

					for (i=0; i<openList.length; i++)
					{//如果在开启列表中 判断是否可以更新原来的元素的父节点（根据G值判断）
						count++;
						if (equal((openList[i] as PathNode).point, tmpSTD))
						{
							exist = true;
							if (tempNode.currentCost <= (openList[i] as PathNode).currentCost )
							{
								openList.splice(i,1);
								openList.push(tempNode);
							}
							break;
						}
					}
//					trace("step3 total cost "+count);
					//step 3.4:可用且不在列表中，则放入开启列表中
					if (!exist)
					{
						openList.push(tempNode);
					}
				}
			}
			//如果找到了结果路径 则依次获取每一个点
			var myPathList:Array = null;
			if (find)
			{
				myPathList =  new Array();
				while (startNode != null)
				{
					myPathList.push(STDToPos(startNode.point));
					startNode = startNode.father;
				}
//				debugPaint(layer, startSTD, destSTD, myPathList);
			}	
			return myPathList;
		}

		//检测新节点 是否可用
		private static function checkAvaible(layer:LayerConfig, currentSTD:Pt):Boolean
		{
//			var boundXLow:int = -10;
//			var boundYLow:int = -10;
//			var boundXHigh:int = 33;
//			var boundYHigh:int = 33;
			if (layer.boundX_Min <= currentSTD.x && layer.boundX_Max >= currentSTD.x 
			&&	layer.boundY_Min <= currentSTD.y && layer.boundY_Max >= currentSTD.y
			&&  currentSTD.x + currentSTD.y >= layer.boundXAY_Min && currentSTD.x + currentSTD.y <= layer.boundXAY_Max
			&&  currentSTD.x - currentSTD.y >= layer.boundXMY_Min && currentSTD.x - currentSTD.y <= layer.boundXMY_Max)
			{
				var layerItemConfig:LayerItemConfig = layer.map[currentSTD.x + " " + currentSTD.y];
 				if (layerItemConfig != null && layerItemConfig.type == LayerItemConfig.TYPE_WALL)
 					return false;
 				else
					return true;
			}
			return false;
		}
		
		//预估函数  决定整个A*算法的好坏
		private static function estimate(currentSTD:Pt, destSTD:Pt):int
		{
			return dist(currentSTD,destSTD);	
		}
		
		//计算直线距离
		private static function dist( pointSTD1:Pt, pointSTD2:Pt):int
		{
			return Math.floor(Math.sqrt( Math.pow((pointSTD1.x - pointSTD2.x),2.0)+Math.pow((pointSTD1.y - pointSTD2.y),2.0) ));
		}
		
		//判断节诶点是否为同一个
		public static function equal(pointSTD1:Pt, pointSTD2:Pt):Boolean
		{
			if (pointSTD1.x == pointSTD2.x && pointSTD1.y == pointSTD2.y)
				return true;
			return false;
		}
		
		//标准化数据点
		public static function posToSTD(originalPt:Pt):Pt
		{
			var destSTD:Pt = new Pt(originalPt.x, originalPt.y, originalPt.z);
			destSTD.x = Math.floor(destSTD.x / TownScene.gridWidth);
			destSTD.y = Math.floor(destSTD.y / TownScene.gridWidth);
			return destSTD;
		}
		
		//地图化数据
		public static function STDToPos(ptSTD:Pt):Pt
		{
			var dest:Pt = new Pt(ptSTD.x, ptSTD.y, ptSTD.z);
			dest.x = dest.x * TownScene.gridWidth;
			dest.y = dest.y * TownScene.gridWidth;
			return dest;
		}
		
		//节点的前进方向
		private static function direction(directions:int):Object
		{
			var direction:Object = null;
			switch(directions)
			{
				case 4:
					direction = {0:{x:0, y:1}, 1:{x: 0,y:-1}, 2:{x:-1,y:0}, 3:{x:1,y: 0}};
					break;
				case 8:
					direction = {0:{x:0, y:1}, 1:{x: 0,y:-1}, 2:{x:-1,y:0}, 3:{x:1,y: 0}, 
								4:{x:-1,y:1}, 5:{x:-1,y:-1}, 6:{x:1 ,y:1}, 7:{x:1,y:-1} };
					break;
				default:
					break;
			}		
			return direction;
		}
		
		//测试运行结果
		private static function debugPaint(layer:LayerConfig, startSTD:Pt, destSTD:Pt, pathList:Array):void
		{
			var tempMap:Object = new Object();
			for (var i:int = layer.boundX_Min; i < layer.boundX_Max; i++)
			{
				for (var j:int = layer.boundY_Min; j < layer.boundY_Max; j++)
				{
					if (layer.map.hasOwnProperty(i+" "+j) )
						tempMap[i+" "+j] = '#';
					else tempMap[i+" "+j] = '.';
				}
			}
			tempMap[startSTD.x+" "+startSTD.y] = "$";
			tempMap[destSTD.x+" "+destSTD.y] = "!";
			for (i = 1; i<pathList.length-1; i++)
			{
				var tempPt:Pt = posToSTD(pathList[i] as Pt);
				tempMap[tempPt.x+" "+tempPt.y] = "@";
			}
			for (i = layer.boundX_Min; i < layer.boundX_Max; i++)
			{
				var t:String = new String();
				for (j = layer.boundY_Min; j < layer.boundY_Max; j++)
				{
					
					t += tempMap[i+" "+j];
				}
				trace(t);
			}
			
		}
	}
}